package array;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring76 {

    @Test
    public void test() {
        minWindow("DBACE", "ABC");
        minWindow("ADOBECODEBANC", "ABC");
        minWindow("a", "aa");
    }

    public String minWindow(String s, String t) {
        int left = 0;
        int right = 0;

        // 满足条件的最小子串下标: [start, end)
        int start = 0;
        int end = Integer.MAX_VALUE;

        Map<Character, Integer> windowCharMap = new HashMap<>(t.length()*3/2);
        Map<Character, Integer> targetCharMap = new HashMap<>(t.length()*3/2);
        int validChars = 0; // 已经满足条件的distinct char的数量

        for (int i = 0; i < t.length(); i++) {
            Character ch = t.charAt(i);
            addCharCount(ch, targetCharMap);
        }

        while (right < s.length()) {
            // 窗口右侧右移一位
            Character ch = s.charAt(right);
            right++; //已经增大了, 不是本次循环的值了

            // 只关心有效字符
            if (targetCharMap.containsKey(ch)) {
                addCharCount(ch, windowCharMap);
                // 有可能前者已经大于后者了, 不会进if
                if (windowCharMap.get(ch).intValue() == targetCharMap.get(ch).intValue()) {
                    // 只在两者刚好相等时增加validChars; 如果前者继续增加, 不再增加validChars
                    validChars++;
                }
            }

            // 记录可行方案
            while (validChars == targetCharMap.size()) {
                if (right - left < end - start) {
                    start = left;
                    end = right;
                }

                // 同时尝试窗口左侧右移一位
                ch = s.charAt(left);
                if (windowCharMap.containsKey(ch)) {
                    // 有可能前者仍然大于后者, 不会进if
                    if (windowCharMap.get(ch).intValue() == targetCharMap.get(ch).intValue()) {
                        // 只在两者刚好相等时减少validChars; 如果前者继续减少, 不再减少validChars
                        validChars--;
                    }
                    addCharCount(ch, windowCharMap, -1);
                }
                left++;
            }
        }
        String sub = (end <= s.length()) ? s.substring(start, end) : "";
        System.out.format("s: %s,  t: %s,  sub: %s\n", s, t, sub);
        return sub;
    }

    public void addCharCount(Character ch, Map<Character, Integer> charMap) {
        addCharCount(ch, charMap, 1);
    }

    public void addCharCount(Character ch, Map<Character, Integer> charMap, int delta) {
        Integer count = charMap.getOrDefault(ch, 0);
        charMap.put(ch, count+delta);
    }
}
